package str;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class strStr {
    public int strStr(String haystack, String needle) {

//        int i = 0;
//        while (i <= haystack.length()-needle.length()){
//            if (haystack.startsWith(needle, i)){
//                return i;
//            }
//            i++;
//        }
//        return -1;
        if (needle.isEmpty()){
            return 0;
        }
        int[] a = new int[needle.length()];
        int[] next = getNext(a, needle);
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)){
                j = next[j-1];
            }
            if (haystack.charAt(i) == needle.charAt(j)){
                j++;
            }
            if (j == needle.length()){
                return (i-needle.length()+1);
            }
        }
        return -1;
    }
    public int[] getNext(int[] next, String s){
        //i后缀末尾位置
        //j前缀末尾
        int j = 0;
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(i)!=s.charAt(j)){
                j = next[j-1];
            }
            if (s.charAt(i) == s.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
